public class IntersectingLinkedLists {

    // 链表节点定义
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    // 查找交点的方法
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode pA = headA;
        ListNode pB = headB;

        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }

        return pA;
    }

    public static void main(String[] args) {
        // 创建示例链表（有交点）
        // 1 -> 2 -> 3 -> 6 -> 7
        //      4 -> 5 ↗
        ListNode common = new ListNode(6);
        common.next = new ListNode(7);

        ListNode headA = new ListNode(1);
        headA.next = new ListNode(2);
        headA.next.next = new ListNode(3);
        headA.next.next.next = common;

        ListNode headB = new ListNode(4);
        headB.next = new ListNode(5);
        headB.next.next = common;

        // 创建示例链表（无交点）
        // 10 -> 20 -> 30
        // 40 -> 50 -> 60
        ListNode headC = new ListNode(10);
        headC.next = new ListNode(20);
        headC.next.next = new ListNode(30);

        ListNode headD = new ListNode(40);
        headD.next = new ListNode(50);
        headD.next.next = new ListNode(60);

        // 测试有交点的情况
        ListNode intersection1 = getIntersectionNode(headA, headB);
        System.out.println("有交点的情况：交点值为 " +
                (intersection1 != null ? intersection1.val : "null"));

        // 测试无交点的情况
        ListNode intersection2 = getIntersectionNode(headC, headD);
        System.out.println("无交点的情况：交点值为 " +
                (intersection2 != null ? intersection2.val : "null"));
    }
}